package sword.offer;

import java.util.Objects;

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Sixteen {
    /**
     * 最简单的方式 就是将x累加n次。 那么时间复杂度为 O(n)
     * 快速幂方法
     * 1.对于偶数次幂
     * x^n 可以表示为  x^(n/2) * x^(n/2)
     * 2. 对于奇数次幂
     * x^n 可以表示为 x^(n/2) * x^(n/2) * x （ps: 在java中 n/2会向下取整）
     * */
    class Solution {
        public double myPow(double x, int n) {
            // 输入异常的情况 ，底数为0并且指数为负数
            if(Objects.equals(x, 0.0) && n < 0){
                throw new RuntimeException("输入数据无效！");
            }
            // 指数为负数的情况下  2的-2次方 是 2的2次方的倒数
            long p = n;
            double result = pow(x, Math.abs(p));
            if(n < 0){
                result = 1.0/result;
            }
            return result;
        }

        double pow(double x, long n){
            if(n == 0){
                return 1;
            }
            if(n == 1){
                return x;
            }
            double result = pow(x, n >> 1);
            result *= result;
            if((n & 1) == 1){
                result *= x;
            }
            return result;
        }
    }
}
